package BFS解决FloodFill算法;

import java.util.*;

public class 单词接龙 {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        Set<String> hash = new HashSet<>();
        for (String s : wordList)
            hash.add(s);

        if (wordList.size() == 0 || !hash.contains(endWord))
            return 0;

        if (beginWord.equals(endWord))
            return 1;

        Set<String> vis = new HashSet<>();
        vis.add(beginWord);
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        int ret = 1;
        while (!q.isEmpty()) {
            ret++;
            int sz = q.size();
            while (sz-- != 0) {
                String tmp = q.poll();
                for (int i = 0; i < tmp.length(); i++) {
                    char[] temp = tmp.toCharArray();
                    for (char j = 'a'; j <= 'z'; j++) {
                        temp[i] = j;
                        String result = String.valueOf(temp);
                        if (hash.contains(result) && !vis.contains(result)) {

                            if (result.equals(endWord))
                                return ret;

                            q.add(result);
                            vis.add(result);
                        }

                    }
                }


            }
        }

        return ret;
    }

}

